﻿using System;
using System.Collections.Generic;

// adapted from http://msdn.microsoft.com/en-us/vcsharp/aa336800.aspx

public class BST<T> where T : IComparable<T> {
    private BinaryNode<T> root;

    public BST() {
        root = null;
    }

    public BST(T data) {
        this.root = new BinaryNode<T>(data);
    }

    public String ToTree() {
        return root.ToTree("|   ", "|___");
    }

    public BinaryNode<T> Root {
        get { return root; }
        set { root = value; }
    }

    public string preorder() {
        return preorder2(root);
    }
    private string preorder2(BinaryNode<T> node) {
        string s = "";
        if (node != null) {
            s += node.Value;
            s += preorder2(node.Left);
            s += preorder2(node.Right);
        }
        return s;
    }

    public string postorder() {
        return postorder2(root);
    }

    private string postorder2(BinaryNode<T> node) {
        string s; // showing an alternative code design
        if (node == null)
            s = "";
        else
            s = postorder2(node.Left) +
              postorder2(node.Right) +
              node.Value;
        return s;
    }

    public string inorder() {
        return inorder2(root);
    }
    private string inorder2(BinaryNode<T> node) {
        string s = "";
        if (node != null) {
            s += inorder2(node.Left);
            s += node.Value;
            s += inorder2(node.Right);
        }
        return s;
    }

    public Boolean isEmpty() {
        return root == null;
    }

    public int getHeight() {
        return root.getHeight();
    }

    public bool naivefind(T target) {
        return root.naivefind(target, root);
    }
  
    public bool Contains(T target) {
        // search the tree for a node that contains data
        BinaryNode<T> current = root;
        int result;
        while (current != null) {
            result = current.Value.CompareTo(target);
            if (result == 0) return true;
            else if (result > 0) current = current.Left;
            else if (result < 0) current = current.Right;
        }
        return false;
    }

    public void Add(T data) {

        // create a new Node instance
        BinaryNode<T> n = new BinaryNode<T>(data);
        int result;

        // now, insert n into the tree
        // trace down the tree until we hit a NULL
        BinaryNode<T> current = root;
        BinaryNode<T> parent = current;
        while (current != null) {
            result = current.Value.CompareTo(data);
            if (result == 0)
                // they are equal - attempting to enter a duplicate - do nothing
                return;
            else if (result > 0) {
                // current.Value > data, must add n to current's left subtree
                parent = current;
                current = current.Left;
            }
            else if (result < 0) {
                // current.Value < data, must add n to current's right subtree
                parent = current;
                current = current.Right;
            }
        }

        // We're ready to add the node!
        if (parent == null)
            // the tree was empty, make n the root
            root = n;
        else {
            result = parent.Value.CompareTo(data);
            if (result > 0)
                // parent.Value > data, therefore n must be added to the left subtree
                parent.Left = n;
            else
                // parent.Value < data, therefore n must be added to the right subtree
                parent.Right = n;
        }
    }

    public bool Delete(T data) {
        // first make sure there exist some items in this tree
        if (root == null)
            return false;       // no items to remove

        // Now, try to find data in the tree
        BinaryNode<T> current = root, parent = null;
        int result = current.Value.CompareTo(data);
        while (result != 0) {
            if (result > 0) {
                // current.Value > data, if data exists it's in the left subtree
                parent = current;
                current = current.Left;
            }
            else if (result < 0) {
                // current.Value < data, if data exists it's in the right subtree
                parent = current;
                current = current.Right;
            }

            // If current == null, then we didn't find the item to remove
            if (current == null)
                return false;
            else
                result = current.Value.CompareTo(data);
        }

        // At this point, we've found the node to remove

        // We now need to "rethread" the tree
        // CASE 1: If current has no right child, then current's left child becomes
        //         the node pointed to by the parent
        if (current.Right == null) {
            if (parent == null)
                root = current.Left;
            else {
                result = parent.Value.CompareTo((T)(current.Value));
                if (result > 0)
                    // parent.Value > current.Value, so make current's left child a left child of parent
                    parent.Left = current.Left;
                else if (result < 0)
                    // parent.Value < current.Value, so make current's left child a right child of parent
                    parent.Right = current.Left;
            }
        }
        // CASE 2: If current's right child has no left child, then current's right child
        //         replaces current in the tree
        else if (current.Right.Left == null) {
            current.Right.Left = current.Left;

            if (parent == null)
                root = current.Right;
            else {
                result = parent.Value.CompareTo((T)(current.Value));
                if (result > 0)
                    // parent.Value > current.Value, so make current's right child a left child of parent
                    parent.Left = current.Right;
                else if (result < 0)
                    // parent.Value < current.Value, so make current's right child a right child of parent
                    parent.Right = current.Right;
            }
        }
        // CASE 3: If current's right child has a left child, replace current with current's
        //          right child's left-most descendent
        else {
            // We first need to find the right node's left-most child
            BinaryNode<T> leftmost = current.Right.Left, lmParent = current.Right;
            while (leftmost.Left != null) {
                lmParent = leftmost;
                leftmost = leftmost.Left;
            }

            // the parent's left subtree becomes the leftmost's right subtree
            lmParent.Left = leftmost.Right;

            // assign leftmost's left and right to current's left and right children
            leftmost.Left = current.Left;
            leftmost.Right = current.Right;

            if (parent == null)
                root = leftmost;
            else {
                result = parent.Value.CompareTo((T)(current.Value));
                if (result > 0)
                    // parent.Value > current.Value, so make leftmost a left child of parent
                    parent.Left = leftmost;
                else if (result < 0)
                    // parent.Value < current.Value, so make leftmost a right child of parent
                    parent.Right = leftmost;
            }
        }

        // Clear out the values from current
        current.Left = current.Right = null;
        current = null;

        return true;
    }

    public T findMin() {
        BinaryNode<T> current = root;
        while (current.Left != null) current = current.Left;
        return current.Value;
    }

    public T findMax() {
        BinaryNode<T> current = root;
        while (current.Right != null) current = current.Right;
        return current.Value;
    }

}
